package leetCode.Test1;

/**
 * @author zwei
 * @create 2024-07-24 18:51
 */
public class gcdOfStrings {
    //对于字符串 s 和 t，只有在 s = t + t + t + ... + t + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。
    //给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 x 能除尽 str2 。
    //示例 1：
    //输入：str1 = "ABCABC", str2 = "ABC"
    //输出："ABC
    //示例 2：
    //输入：str1 = "ABABAB", str2 = "ABAB"
    //输出："AB"

    public String gcdOfStrings(String str1, String str2) {
        int len1 = str1.length(), len2 = str2.length();
        for (int i = Math.min(len1, len2); i >= 1; --i) { // 从长度大的开始枚举
            if (len1 % i == 0 && len2 % i == 0) {
                String X = str1.substring(0, i);
                if (check(X, str1) && check(X, str2)) {
                    return X;
                }
            }
        }
        return "";
    }

    /**
     * 判断str1是否是由str2重复若干次构成的
     * @param str1
     * @param str2
     * @return
     */
    public boolean check(String str1, String str2) {
        int lenx = str2.length() / str1.length();
        StringBuffer ans = new StringBuffer();
        for (int i = 1; i <= lenx; ++i) {
            ans.append(str1);
        }
        return ans.toString().equals(str2);
    }

}
